package com.cyx;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

/**
 * @author 陈裕星
 * @version 1.0
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 */
public class N皇后 {
    static List<List<String>> res = new ArrayList<>();
    static int n;
    static boolean[][] board;
    static HashSet<Integer> col,pie,na;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();//几皇后
        board = new boolean[n][n];
        col = new HashSet<>();
        pie = new HashSet<>();
        na = new HashSet<>();
        //找出所有解
        dfs(0);
        System.out.println(n + "皇后问题总共有：" + res.size() + "解法");
        System.out.println(res.toString());
    }

    /**
     *
     * @param i:要放置皇后的层级
     */
    static void dfs(int i){
        if(i == n){
            //将生成好的boolean数组添加进去
            List<String> list = generate_result(board);
            res.add(list);
            return;
        }

        for (int j = 0; j < n; j++) {
            //是否可放置的判断
            if (col.contains(j) || pie.contains(i+j) || na.contains(i-j)) continue;
            board[i][j] = true;
            col.add(j);
            pie.add(i+j);//左对角线相加为常数
            na.add(i-j);//右对角线相减为常数
            //递归
            dfs(i+1);
            //回溯
            board[i][j] = false;
            col.remove(j);
            pie.remove(i+j);
            na.remove(i-j);
        }
    }
    static List<String> generate_result(boolean[][] board){
        List<String> tmp = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < board[0].length; j++) {
                if(board[i][j]){
                    sb.append('Q');
                }else{
                    sb.append('.');
                }
            }
            tmp.add(sb.toString());
        }
        return tmp;
    }
}
